Problem statement: zenit14kkg

Keďže úloha s umiestnením zvierat do sály mala na školskom kole taký ohromný úspech, zvieratká sa rozhodli, že si pre vaše potešenie vymyslia ešte jeden podobný problém. V tomto probléme pôjdeme trocha viac do hĺbky a budeme uvažovať účastníkov stretnutia individuálne.

Po vzore rytierov kráľa Artuša si zvieratká organizujú stretnutia za okrúhlym stolom. Niektoré zvieratká sa ale nachádzajú na jedálničku niektorých iných. Takáto dvojca samozrejme nemôže sedieť vedľa seba.

Na prvom riadku vstupu je počet zvierat \(N\) (\(3 \leq N \leq 9\)) a počet nebezpečných dvojíc \(P\) (\(0 \leq P \leq N\cdot(N-1)/2\)). Zvieratká si očíslujeme od 1 po \(N\). Na každom zo zvyšných \(P\) riadkov je dvojica rôznych celých čísel medzi 1 a \(N\) vrátane, ktorá hovorí, že ak tieto zvieratká budú sedieť vedľa seba, zasadnutie sa zmení na hostinu. Každá dvojica je na vstupe uvedená najviac raz.

V prípade, že vyhovujúce rozsadenie neexistuje, vypíšte NEDA SA. V opačnom prípade vypíšte na jeden riadok poradie, v akom budú zvieratká sedieť vedľa seba v kruhu. V tejto postupnosti sa musí každé z čísel 1 až \(N\) vyskytnúť práve raz. Medzi každými dvoma susednými zvieratkami vypíšte jednu medzeru. Ak existuje viacero korektných rozsadení, vypíšte ľubovoľné.

Všimnite si, že výpis nie je jednoznačný. Napríklad [3 1 2], [1 2 3] a [3 2 1] označujú to isté rozsadenie a líšia sa tým, ktorý prvok sme vypísali ako prvý, prípadne či sa na kruh pozeráme v smere hodinových ručičiek alebo opačne. Ak je toto rozsadenie správne, môžete si vybrať ľubovoľný z týchto výpisov. Pamätajte len, že okrem prvkov, ktoré idú za sebou vo vypísanom poradí susedí v kruhu aj posledný s prvým.

Príklady

Input:

4 1
1 3

Output:

2 1 4 3

Jednotka musí mať susedov 2 a 4.

Input:

6 6
1 2
1 6
5 6
1 4
6 2
4 2

Output:

NEDA SA

Input:

9 0

Output:

4 7 9 1 5 3 2 6 8

Mohli sme vypísať aj hociktorú inú zo zvyšných 40319 možností.